17. 函数式编程 Functional Programming

本节的内容涉及到了一些核心的概念与思考问题的模型，请务必反复温习确保能够完全理解这些概念与模型背后的思想并能融会贯通在实际的开发过程中。

函数式编程的规定如下：

所有函数都是 纯函数。
所有对象都是 不可变的。
一旦将某个对象绑定到某个名字上，这个绑定关系就 不可更改。无法对这个命名进行重新赋值。

函数式编程是对过程的抽象，关注函数的动作。

我们先前已经接触过了一些与函数式编程有关的概念，见：4. 高阶函数 Higher-order Functions。

上面的规定带来的一个最大的好处就是 引用透明（Referential Transparency），即所有表达式的值不会因为改变该表达式的求值顺序或将某个子表达式改为该表达式的值而改变。这就为并行或懒惰计算提供了空间。

本部分所述的内容可能是一个很难理解的概念！

然而，由于上述规定，函数式编程中无法出现 for 与 while 这种会将变量重新赋值的行为，而它们是进行迭代的核心工具。然而，函数式编程仍然可以借助 尾递归（Tail Recursion） 来实现迭代，无需使用时空开销要高得多的普通递归。

例如下面是阶乘函数的递归实现与迭代实现：

def fact_iter(n):
	ans, i = 1, 1
	while i <= n:
		ans, i = ans*i, i+1
	return ans

def fact_rec(n):
	if n == 0:
		return 1
	else:
		return n * fact_rec(n-1)

可以发现，虽然两种实现的时间复杂度均为 $Θ (n)$ ，但递归实现与迭代实现的空间复杂度分别为 $Θ (n)$ 与 $Θ (1)$ 。究其原因，是递归实现中递归深度每加一就需要向栈区压入一个新的帧存储形参与返回值。然而，通过尾递归，有可能就使这些递归调用只占用恒定的内存空间，这就需要引入 尾调用（Tail Call） 的概念：

尾调用即为在 尾上下文（Tail Context） 中发生的函数调用。一般而言，尾上下文指的是某些特定的语法位置，在这些位置中发生的函数调用属于尾调用。常见的尾上下文包括：

函数体的最后一个表达式。
对某些具有特殊执行顺序的语句而言，如果它们整个语句是函数体的最后一个表达式，则下述表达式是尾上下文：
- if 语句的两个分支。
- cond、case、and、or 的最后一个子表达式。
- begin 块的最后一个表达式。

尾调用举例

def f1():
	return f() # YES

def f2():
	x = f() # NO
	return x

def f3():
	return f() + 1 # NO

def f4():
	# g, h are all tail calls
	if p():
		return g()
	else:
		return h()

def f5():
	return f() and g() # g is tail call while f isn't

用通俗的语言来说，当一个函数要执行的最后一个语句是一个函数调用时，这个函数调用就属于尾调用。

对于一个递归函数，如果它的每一个递归调用都是尾调用，则该函数是一个 尾递归函数。

在常规递归中，由于递归调用表达式并不是本层调用需要求值的最后一个表达式，解释器在进行递归时必须在调用栈中新建一个栈帧，保存当前函数的参数、局部变量和返回地址以允许调用结束后继续执行后续操作。在这种情况下栈深度随着递归次数线性增长，可能导致栈溢出。而在尾递归中，由于尾递归中，函数的最后一步操作是递归调用自身，即没有后续操作需要执行，解释器可以直接覆盖当前栈帧的参数和局部变量，此时栈深度不再随递归次数增加，可以说这一行为完全等价于迭代循环。

例如，我们直接给出阶乘函数的尾递归实现：

def fact_tail(n, k = 1):
	if n == 0:
		return k
	else:
		return fact_tail(n - 1, k * n)

这个函数看起来与上面的递归实现没有什么差别...

我们可以将两个函数的环境图放在这里：

Pasted image 20250330213958.png

Pasted image 20250330214033.png

与普通的递归写法相比，尾递归将所需的所有中间结果 直接通过参数传递给了下一层，因此，最终的递归结果 就等于最内层递归调用表达式的值，而中间所有的递归过程只是在传递运算中的一个状态。换言之，每当进行下一次递归时，不会用到任何前面递归所存储的状态，因而，每进入新一层的递归，前面的递归帧所占用的空间可以直接回收。这样就实现了在常数时间复杂度下完成递归。

Python 原生并不会自动识别尾调用函数并进行优化。但我们可以自己编写尾调用的优化函数。其中一种优化方法被叫做 蹦床函数（Trampolining Function）。其基本思想是：将所有函数调用封装为 Thunk，需要时再拆开 thunk 实施调用，以此将递归执行转化为迭代执行。Thunk 是一类函数的别名，主要特征是对另外一个函数添加了一些额外的操作，类似 5. 装饰器 Decorator。其主要用途为延迟函数执行（惰性求值）或者给一个函数执行前后添加一些额外的操作。由于递归调用不会立刻执行而是先封装在 thunk 中，Python 解释器就不会创建新的帧，省下了大量空间。

我们将上面的尾递归阶乘函数进一步封装得到下面的形式：

def thunk_factorial(n, so_far=1):
    def thunk():
        if n == 0:
            return so_far
        return thunk_factorial(n - 1, so_far * n)
    return thunk

def factorial(n):
    value = thunk_factorial(n)
    while callable(value): # While value is still a thunk
        value = value()
    return value

上面的函数通过相互调用，阶乘函数内部每次执行完一层递归后会获得代表深一层调用的还未进行调用的 thunk，而老的调用完的 thunk 已经被丢弃，函数执行过程中最多只会有一个活跃的 thunk 与 thunk_factorial。因此实现了常数级别的空间占用。见下图：

Pasted image 20250511210950.png

对于需要大量使用到递归的函数式语言（例如 Lisp 与 Haskell），其语言规范中强制要求了解释器必须实现尾递归的优化。